package Year22_Month06.day25;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 组合总和2_方法二 {
    static List<List<Integer>> list = new LinkedList<>();
    static LinkedList<Integer> path = new LinkedList<>();
    static int Target;
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] arr = new boolean[candidates.length];//创建一个boolean数组进行标记
        Target = target;
        backstracting(candidates,arr,0,0);
        return list;
    }

    public static void backstracting(int[] candidates,boolean[] arr,int startIndex,int sum){
        if(sum == Target){
            list.add(new LinkedList<>(path));
        }

        for (int i = startIndex; i < candidates.length && sum <= Target; i++) {
            if(i > 0 && arr[i] == arr[i - 1] && arr[i - 1] == false){
                continue;
            }
            arr[i] = true;
            path.add(candidates[i]);
            backstracting(candidates,arr,i + 1,sum + candidates[i]);
            arr[i] = false;
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] candidates = {10,1,2,7,6,1,5};
        System.out.println(combinationSum2(candidates,8));
    }
}
